// https://leetcode.cn/problems/next-permutation/
// Created by ade on 2022/8/17.
// 必须 原地 修改，只允许使用额外常数空间。 如果当前排列是最大的，则返回最小的那个排列
/*
 * 1,2 直接交换
 *
 * 3,2,1 123 132
 *
 * 1,3,4,2
 *
 * 1,4,3,2 ==  2431  2134
 * 4,3,2,1 == 1324 1234
 *
 *
 * 1,3,2,4 == 1342
 *
 * 1,7,6,5,4,3,2 == 2134567
 *
 * 4,5,2,8,7,6,3,1  4,5,3,8,7,6,2,1
 *
 * */

#include <iostream>
#include <vector>
#include <algorithm>


using namespace std;

class Solution {
public:
    void nextPermutation(vector<int> &nums) {
        bool flag = true;
        int len = nums.size();

        // 找出第一个后面大于前面的index
        int firstIndex = -1;
        for (int i = len - 1; i >= 1; i--) {

            if (nums[i] > nums[i - 1]) {
                firstIndex = i - 1;
                flag = false;
                break;
            }
        }
        if (!flag) {
            for (int i = len - 1; i >= 1; i--) {
                if (nums[i] > nums[firstIndex]) {
                    swap(nums[i], nums[firstIndex]);
                    break;
                }
            }
            sort(nums.begin() + firstIndex + 1, nums.end());
        } else {
            sort(nums.begin(), nums.end());
        }
    }
};

int main() {
    Solution so;
    vector<int> nums = {1, 2}; // 1,3,2,4
//    vector<int> nums = {1, 4, 3, 2}; // 2,1,3,4
    so.nextPermutation(nums);
    for (auto i : nums) {
        cout << i << ",";
    }
    cout << endl;
    return 0;
}